#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int start = 0, end = nums.size() - 1;
        int level = nums[start];
        if (nums.size() == 1)
            return nums[0] == target ? 0 : -1;
        if (nums.size() == 2)
            return nums[0] == target ? 0 : nums[1] == target ? 1
                                                             : -1;
        while (start <= end)
        {
            int i = (start + end) / 2;
            if (target >= level)
            {
                if (nums[i] < level)
                    end = i - 1;
                else if (nums[i] < target)
                    start = i + 1;
                else if (nums[i] > target)
                    end = i - 1;
                else
                    return i;
            }
            else
            {
                if (nums[i] >= level)
                    start = i + 1;
                else if (nums[i] < target)
                    start = i + 1;
                else if (nums[i] > target)
                    end = i - 1;
                else
                    return i;
            }
        }
        return start > 0 && start < nums.size() && nums[start] == target ? start : -1;
    }
};

int main()
{
    cout << "Code33" << endl;
    Solution s;
    vector<int> nums = {5, 1, 2, 3, 4};
    cout << s.search(nums, 1) << endl;
    return 0;
}